package arithmetic.LeetCode;

import utils.ListNodeUtils;
import utils.ListNodeUtils.ListNode;

/**
 * 链表归并排序
 *
 * @author jiangfeng on 2023/6/21
 */
public class SortList {
    public static void main(String[] args) {
        // ListNodeUtils.printLink(ListNodeUtils.createLink(2, 1, 3, 5, -1, 4));
        // ListNodeUtils.printLink(new Solution().sortList(ListNodeUtils.createLink(2, 1, 3, 5, -1, 4)));
//        ListNodeUtils.printLink(new Solution().sortList(ListNodeUtils.createLink(4,2,1,3)));
        ListNodeUtils.printLink(new Solution().sortList(
                ListNodeUtils.createLink(50000, 49999, 49998, 49997, 49996, 49995, 49994, 49993, 49992,
                        49991, 49990)));
    }

    static class Solution {
        // 自底向上
        public ListNode sortList(ListNode head) {
            if(head==null || head.next==null){
                return head;
            }
            int num =0;
            ListNode numIndex = head;
            while(numIndex!=null){
                num++;
                numIndex = numIndex.next;
            }
            ListNode tempHead = new ListNode(-1);
            tempHead.next=head;
            for(int step = 1;step<=num;step=step*2){
                ListNode preNext = tempHead;
                ListNode index =  tempHead.next;
                while(index!=null && index.next!=null){
                    // 第一段
                    ListNode head1 = index;
                    int i =1;
                    while(index!=null && i<step){
                        i++;
                        index=index.next;
                    }
                    if(index==null||index.next==null){
                        continue;
                    }
                    ListNode tail1 = index;
                    ListNode head2 = tail1.next;
                    tail1.next=null;

                    // 第二段
                    index=head2;
                    i=1;
                    while(index!=null && i<step){
                        i++;
                        index=index.next;
                    }

                    ListNode tail2 = index;
                    if(index!=null){
                        index = tail2.next;
                        tail2.next=null;
                    }
                    // 合并两段
                    ListNode newHead = merge(head1,head2);
                    // 接上
                    preNext.next=newHead;

                    // 找到尾巴
                    ListNode tempNewTail =  newHead;
                    while(tempNewTail.next!=null){
                        tempNewTail=tempNewTail.next;
                    }
                    tempNewTail.next=index;
                    preNext = tempNewTail;
                }

            }
            return tempHead.next;
        }


        public ListNode merge(ListNode head1,ListNode head2){
            ListNode temp = new ListNode(-1);
            ListNode index = temp;
            while(head1!=null && head2!=null){
                if(head1.val<head2.val){
                    index.next=head1;
                    head1=head1.next;
                }else{
                    index.next=head2;
                    head2=head2.next;
                }
                index=index.next;

            }
            if(head1==null){
                index.next=head2;
            }
            if(head2==null){
                index.next=head1;
            }
            return temp.next;
        }
    }

    static class Solution7 {

            // 1.归并排序
            public ListNode sortList(ListNode head) {
                if(head==null || head.next==null){
                    return head;
                }
                ListNode center = getCenterNode(head);
                ListNode next = center.next;
                // 先切掉
                center.next=null;
                ListNode f = sortList(head);
                ListNode s = sortList(next);
                return merge(f,s);
            }

            public ListNode getCenterNode(ListNode head){
                ListNode fast=head.next,slow = head;
                while(fast!=null && fast.next!=null){
                    slow=slow.next;
                    fast=fast.next.next;
                }
                return slow;
            }

            public  ListNode merge(ListNode node1,ListNode node2){
                ListNode tempHead = new ListNode(),index= tempHead;

                while(node1!=null&& node2!=null){
                    if(node1.val>node2.val){
                        index.next=node2;
                        node2=node2.next;
                    }else{
                        index.next=node1;
                        node1=node1.next;
                    }
                    index=index.next;
                }
                if(node1==null){
                    index.next=node2;
                }
                if(node2==null){
                    index.next=node1;
                }
                return tempHead.next;
            }

            //2. 自底向上

            //3.快排
    }

    static class Solution6 {

            public ListNode sortList(ListNode head) {
                // 快排版本, 不断用二分法,选定一个基准数. 比他大的放右边,比他小的放左边.
                if(head==null || head.next==null){
                    return head;
                }
                // 选取头做 基准数.

                ListNode pivatNode = getCenterNode(head);
                int p = pivatNode.val;
                // 选取中间数做基准数.

                // 存放比基准数小的listNode
                ListNode lTemp = new ListNode(0);
                ListNode headTemp = new ListNode(0,head);
                ListNode index = headTemp,l=lTemp;
                while(index.next!=null&&index.next!=pivatNode){
                    if(index.next.val<p){
                        l.next=index.next;
                        l=l.next;
                        // 原链切断.顺便跳下一个节点,参考86分隔链表
                        index.next=index.next.next;
                    }else{
                        index=index.next;
                    }
                }
                // 跳过 pivatNode 继续
                index.next=pivatNode.next;
                //index=pivatNode;
                while(index.next!=null){
                    if(index.next.val<p){
                        l.next=index.next;
                        l=l.next;
                        // 原链切断.顺便跳下一个节点,参考86分隔链表
                        index.next=index.next.next;
                    }else{
                        index=index.next;
                    }
                }
                // 左边得切断,要不然死循环
                l.next=null;

                ListNode ls = sortList(lTemp.next);
                ListNode rs = sortList(headTemp.next);

                // 合并
                if(ls!=null){
                    headTemp.next=ls;
                    while(ls.next!=null){
                        ls=ls.next;
                    }
                    ls.next=pivatNode;
                }else{
                    headTemp.next=pivatNode;
                }
                pivatNode.next=rs;
                return headTemp.next;
            }


            public int getNodeSize(ListNode node){
                int i =0;
                while(node!=null){
                    i++;
                    node=node.next;
                }
                return i;
            }

            public ListNode getCenterNode(ListNode node){
                ListNode fast = node,low=node;
                while(fast!=null && fast.next!=null){
                    fast=fast.next.next;
                    low=low.next;
                }
                return low;
            }


    }

    static class Solution5 {
        public ListNode sortList(ListNode head) {
            // 快排版本, 不断用二分法,选定一个基准数. 比他大的放右边,比他小的放左边.
            if (head == null || head.next == null) {
                return head;
            }
            int p = head.val;
            ListNode lTemp = new ListNode(0);
            ListNode rTemp = new ListNode(0);
            ListNode index = head, l = lTemp, r = rTemp;

            while (index.next != null) {
                if (index.next.val > p) {
                    r.next = index.next;
                    r = r.next;
                } else {
                    l.next = index.next;
                    l = l.next;
                }
                index = index.next;
            }
            // 右边得切断,要不然死循环
            r.next = null;
            l.next = null;

            ListNode ls = sortList(lTemp.next);
            ListNode rs = sortList(rTemp.next);

            // 合并.
            ListNode tempHead = new ListNode(0);
            if (ls != null) {
                tempHead.next = ls;
                while (ls.next != null) {
                    ls = ls.next;
                }
                ls.next = head;
            } else {
                tempHead.next = head;
            }
            head.next = rs;
            return tempHead.next;
        }
    }

    static class Solution1 {
        // 非递归版,自底向上, 先从最小单位1开始合并,每次*2.直到总长度的二分之一.
        public ListNode sortList(ListNode head) {
            // 计算链表总长度.
            ListNode index = head;
            int len = 0;
            while (index != null) {
                len++;
                index = index.next;
            }
            ListNode tempHead = new ListNode(0, head);

            // 开始从1开始
            for (int subLength = 1; subLength <= len; subLength *= 2) {
                // 第一个头
                ListNode pre = tempHead, cur = tempHead.next;
                // 找到第一个尾开始切
                while (cur != null) {
                    ListNode head1 = cur;
                    for (int i = 1; i < subLength; i++) {
                        if (cur != null) {
                            cur = cur.next;
                        }
                    }

                    ListNode next = null;
                    if (cur != null) {
                        next = cur.next;
                    }
                    //if (next == null) {
                    // 已经切完了不需要再合并,继续下一个
                    //  break;
                    //}
                    // 切断一个
                    cur.next = null;
                    // 再切第二个
                    cur = next;
                    ListNode head2 = next;
                    for (int i = 1; i < subLength; i++) {
                        if (cur != null) {
                            cur = cur.next;
                        }
                    }
                    // 切断第二个
                    next = null;
                    if (cur != null) {
                        next = cur.next;
                        cur.next = null;
                    }
                    ListNode temp = merge(head1, head2);
                    //和上一个头合并
                    pre.next = temp;
                    while (temp.next != null) {
                        temp = temp.next;
                    }
                    // 尾巴是下一个的头.
                    pre = temp;
                    cur = next;
                }
            }
            return tempHead.next;

        }
        // 归并排序: 先递归切成两两,再合并


        public ListNode merge(ListNode node1, ListNode node2) {
            if (node1 == null) {
                return node2;
            }
            if (node2 == null) {
                return node1;
            }
            ListNode tempHead = new ListNode();
            ListNode index = tempHead;
            while (node1 != null || node2 != null) {
                if (node1 == null) {
                    index.next = node2;
                    break;
                }
                if (node2 == null) {
                    index.next = node1;
                    break;
                }
                if (node1.val > node2.val) {
                    index.next = node2;
                    node2 = node2.next;
                } else {
                    index.next = node1;
                    node1 = node1.next;
                }
                index = index.next;
            }

            return tempHead.next;
        }

    }

    static class Solution2 {
        // 归并排序: 先递归切成两两,再合并
        public ListNode sortList(ListNode head) {
            return mergeSort(head);
        }

        public ListNode mergeSort(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // 找中点
            ListNode quick = head.next.next;
            ListNode slow = head;
            while (quick != null && quick.next != null) {
                slow = slow.next;
                quick = quick.next.next;
            }

            ListNode temp = slow.next;
            slow.next = null;
            // 先排右,再切链排左
            ListNode node1 = mergeSort(temp);
            ListNode node2 = mergeSort(head);
            // 最后合并
            return merge(node1, node2);
        }

        public ListNode merge(ListNode node1, ListNode node2) {
            if (node1 == null) {
                return node2;
            }
            if (node2 == null) {
                return node1;
            }
            ListNode tempHead = new ListNode();
            ListNode index = tempHead;
            while (node1 != null || node2 != null) {
                if (node1 == null) {
                    index.next = node2;
                    break;
                }
                if (node2 == null) {
                    index.next = node1;
                    break;
                }
                if (node1.val > node2.val) {
                    index.next = node2;
                    node2 = node2.next;

                } else {
                    index.next = node1;
                    node1 = node1.next;
                }
                index = index.next;
            }

            return tempHead.next;
        }


    }
}

